package com.example.learn

import kotlin.math.*
import kotlin.random.Random

fun main() {
    val head = ListNode(Random.nextInt(100), null)
    var cur: ListNode? = null
    var pre: ListNode
    for (i in 0 .. 15) {
        pre = ListNode(Random.nextInt(100), null)
        if (head.next == null) {
            head.next = pre
        }
        if (cur != null) {
            cur.next = pre
        }
        cur = pre
    }
    var tmp: ListNode? = head
    while (tmp != null) {
        print("->" + tmp.value)
        tmp = tmp.next
    }
    println()
    tmp = mergeSort(head, 17)
    while (tmp != null) {
        print("->" + tmp.value)
        tmp = tmp.next
    }
    println()
}

fun mergeSort(head: ListNode?, length: Int) : ListNode? {
    if (head == null || length < 2) return head
    val middle = floor(length / 2.0).toInt()
    var index = 1
    val leftHead: ListNode? = head
    var rightHead: ListNode? = null
    val rightLength = length - middle
    var cur = head
    while (cur != null) {
        if (middle <= index) {
            rightHead = cur.next
            cur.next = null
            break
        }
        cur = cur.next
        index ++
    }
    var tmp = leftHead
    while (tmp != null) {
        print("->" + tmp.value)
        tmp = tmp.next
    }
    println()
    tmp = rightHead
    while (tmp != null) {
        print("->" + tmp.value)
        tmp = tmp.next
    }
    println()
    return merge(mergeSort(leftHead, middle), mergeSort(rightHead, rightLength))
}

fun merge(leftHead: ListNode?, rightHead: ListNode?) : ListNode? {
    val head = ListNode(0, null)
    var curr: ListNode? = head
    var tmpLeftHead: ListNode? = leftHead
    var tmpRightHead: ListNode? = rightHead
    while (tmpLeftHead != null && tmpRightHead != null) {
        if (tmpLeftHead.value <= tmpRightHead.value) {
            curr?.next = tmpLeftHead
            curr = tmpLeftHead
            tmpLeftHead = tmpLeftHead.next
        } else {
            curr?.next = tmpRightHead
            curr = tmpRightHead
            tmpRightHead = tmpRightHead.next
        }
    }
    if (tmpLeftHead == null) {
        curr?.next = tmpRightHead
    } else {
        curr?.next = tmpLeftHead
    }
    var tmp = head.next
    while (tmp != null) {
        print("->" + tmp.value)
        tmp = tmp.next
    }
    println()
    return head.next
}


data class ListNode(val value: Int,  var next: ListNode?)